1. Field of the Invention
This invention relates generally to the field of computer systems and, more particularly, to communications protocols within computer systems and/or networks, and communication routing or switching within interconnection fabrics.
2. Description of the Related Art
Computer systems are placing an ever-increasing demand on data storage systems. In many of the data storage systems in use today, data storage arrays are used. The interconnection solutions for many large storage arrays are based on bus architectures such as small computer system interconnect (SCSI) or fibre channel (FC). In these architectures, multiple storage devices such as disks may share a single set of wires, or a loop in the case of FC, for data transfers.
Such architectures may be limited in terms of performance and fault tolerance. Since all the devices share a common set of wires, only one data transfer may take place at any given time, regardless of whether or not all the devices have data ready for transfer. Also, if a storage device fails, it may be possible for that device to render the remaining devices inaccessible by corrupting the bus. Additionally, in systems that use a single controller on each bus, a controller failure may leave all the devices on its bus inaccessible.
There are several existing solutions available, which are briefly described below. One solution is to divide the devices into multiple subsets utilizing multiple independent buses for added performance. Another solution suggests connecting dual buses and controllers to each device to provide path fail-over capability, as in a dual loop FC architecture. An additional solution may have multiple controllers connected to each bus, thus providing a controller fail-over mechanism.
In a large storage array, component failures may be expected to be fairly frequent. Because of the higher number of components in a system, the probability that a component will fail at any given time is higher, and accordingly, the mean time between failures (MTBF) for the system is lower. However, the above conventional solutions may not be adequate for such a system. In the first solution described above, the independent buses may ease the bandwidth constraint to some degree, but the devices on each bus may still be vulnerable to a single controller failure or a bus failure. In the second solution, a single malfunctioning device may still potentially render all of the buses connected to it, and possibly the rest of the system, inaccessible. This same failure mechanism may also affect the third solution, since the presence of two controllers does not prevent the case where a single device failure may force the bus to some random state.
Devices in a network or fabric need to be able to communicate with one another. For example, one device may need to send a message to another device corresponding to an operation that first device seeks to perform with the other device's assistance. Communications between devices in an interconnection fabric can be enabled by encoding directions within the messages on how they should be routed through the fabric. For example, a message can be sent along a route in an interconnection fabric comprising several nodes by encoding the route as a list of the node identifiers. The node identifiers uniquely identify each node in the interconnection fabric. For example, the node identifiers might specify coordinates that locate a node in the interconnection fabric. The encoded route might list the node identifiers of each node the message needs to pass through to reach its destination. Another method, used to send messages when nodes in the fabric are capable of being described by coordinates, implicitly specifies the route by providing the coordinates of the sending and receiving nodes. This method allows routes to be calculated from the difference between the two coordinates.
Alternately, the only routing information encoded in the message might be the node identifier of the destination node. The route could then be chosen on the fly. For example, this on-the-fly route might be created by making random turns. Each turn might be made so that the message is brought closer to the destination node. This method provides more flexibility to circumvent faults in the interconnection fabric than some methods, but it may also require more complicated routing circuitry. Yet another method of sending messages involves simply sending the message to all the nodes or devices in the interconnection fabric. This is done by having each node transmit the message to all the nodes it is connected to except the ones from which it received the message. Each node then tries to match its own identifier to that of the destination node encoded in the message.
While all of these methods effectively transmit messages, the use of node identifiers necessarily limits the scalability of the fabric. For example, using 4-bit node identifiers confines the fabric to a maximum size of 16 nodes. If the interconnection fabric exceeds this size, the size of the node identifiers will have to be increased. Identifier size can also limit the shape of the fabric. For example, if a 4-bit identifier contained two 2-bit fields corresponding to the x, y coordinates of each node in a mesh, the mesh could measure 4×4 nodes but could not measure 8×2 nodes, even though both shapes contain 16 nodes, because the latter shape could not be described with 2-bit identifiers.
Another problem with existing routing methods is that they have a limited ability to describe alternate paths between nodes or devices. If independent paths are available between devices or nodes in a network or interconnection fabric, communications are more robust because all of the independent paths must develop errors before communications between the devices or nodes are disrupted. Thus it is desirable to have a routing system capable of using all available independent paths so that communications are less susceptible to errors.
A routing system that lists the identifier of each node along the route can identify all independent paths, but this system still has scalability limitations mentioned above. Encoding schemes that require calculation may be designed to only calculate paths in certain ways, such as by subtracting a sender coordinate from a destination coordinate. In a scheme like this, the calculation may also be unable to identify all of the available independent routes. Similarly, routing systems that calculate routes on the fly by always turning in a certain direction will not be able to identify independent paths that require turning in a different direction. In these situations, the benefit of having multiple independent paths is lost.